﻿#include "state.h"
using namespace std;
state::state(string current_state)
{
    s=current_state;
}
vector<string> solve(string start) {
    string end = "12345678x";
    queue<state> q;
    unordered_map<string, int> visited;

    q.push(state(start));
    visited[start] = 0;
    int x_move[] = { -1,0,1,0 };
    int y_move[] = { 0,1,0,-1 };
    while (q.size()) {
        auto temp = q.front();
        q.pop();
        //依次出队，寻找更多的状态
        int dis = visited[temp.s];
        if (temp.s == end) {
            return temp.moves;
        }
        int index = temp.s.find('x');
        int x_index = index / 3;
        int y_index = index % 3;
        for (int i = 0; i < 4; ++i) {
            int new_x = x_index + x_move[i];
            int new_y = y_index + y_move[i];
            string move = "";
            if (i == 0) {
                move = "up";
            }
            else if (i == 1) {
                move = "right";
            }
            else if (i == 2) {
                move = "down";
            }
            else {
                move = "left";
            }
            //i=0:up,i=1:right,i=2:dowm,i=3:left
            if (new_x >= 0 && new_x < 3 && new_y >= 0 && new_y < 3) {
                swap(temp.s[index], temp.s[new_x * 3 + new_y]);
                if (!visited.count(temp.s)) {
                    temp.moves.push_back(move);
                    visited[temp.s] = dis + 1;
                    q.push(temp);
                    temp.moves.pop_back();

                }
                swap(temp.s[index], temp.s[new_x * 3 + new_y]);
            }
        }
    }
}
